{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Least Operators to Express Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: leastOpsExpressTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #表示数字的最少运算符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数 <code>x</code>，我们将会写出一个形如&nbsp;<code>x (op1) x (op2) x (op3) x ...</code>&nbsp;的表达式，其中每个运算符&nbsp;<code>op1</code>，<code>op2</code>，… 可以是加、减、乘、除（<code>+</code>，<code>-</code>，<code>*</code>，或是&nbsp;<code>/</code>）之一。例如，对于&nbsp;<code>x = 3</code>，我们可以写出表达式&nbsp;<code>3 * 3 / 3 + 3 - 3</code>，该式的值为 3 。</p>\n",
    "\n",
    "<p>在写这样的表达式时，我们需要遵守下面的惯例：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>除运算符（<code>/</code>）返回有理数。</li>\n",
    "\t<li>任何地方都没有括号。</li>\n",
    "\t<li>我们使用通常的操作顺序：乘法和除法发生在加法和减法之前。</li>\n",
    "\t<li>不允许使用一元否定运算符（<code>-</code>）。例如，“<code>x - x</code>” 是一个有效的表达式，因为它只使用减法，但是 “<code>-x + x</code>” 不是，因为它使用了否定运算符。&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>我们希望编写一个能使表达式等于给定的目标值 <code>target</code> 且运算符最少的表达式。返回所用运算符的最少数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 3, target = 19\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>3 * 3 + 3 * 3 + 3 / 3 。表达式包含 5 个运算符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 5, target = 501\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5 。表达式包含 8 个运算符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 100, target = 100000000\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>100 * 100 * 100 * 100 。表达式包含 3 个运算符。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= x &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 2 * 10<sup>8</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [least-operators-to-express-number](https://leetcode.cn/problems/least-operators-to-express-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [least-operators-to-express-number](https://leetcode.cn/problems/least-operators-to-express-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n19', '5\\n501', '100\\n100000000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\r\n",
    "        mx = int(math.log2(target)/math.log2(x))+1 #先确定x可能的最高幂次\r\n",
    "        def dfs(left):\r\n",
    "            if left<=x:\r\n",
    "                return min(2*left-1,2*(x-left))\r\n",
    "            pw = bisect_right(range(mx+1),left,key=lambda k: x**k) #找到最小的越过left的x的幂次\r\n",
    "            ans = 10**9\r\n",
    "            if x**pw-left<left:\r\n",
    "                ans = pw+dfs(x**pw-left) # 已经越过left，放上pw-1个乘号和一个减号，继续递归\r\n",
    "            ans = min(ans,pw-1+dfs(left-x**(pw-1))) # 还没到left，放上pw-2个乘号和一个加号，继续递归\r\n",
    "            return ans\r\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        cost = list(range(40))\n",
    "        cost[0] = 2\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, tgt):\n",
    "            if tgt == 0:\n",
    "                return 0\n",
    "            if tgt == 1:\n",
    "                return cost[i]\n",
    "            if i >= 39:\n",
    "                return inf\n",
    "\n",
    "            t, r = divmod(tgt, x)\n",
    "            return min(r * cost[i] + dfs(i + 1, t),\n",
    "                       (x - r) * cost[i] + dfs(i + 1, t + 1))\n",
    "\n",
    "        return dfs(0, target) -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        pos, neg, k, pos2, neg2 = 0, 0, 0, 0, 2 * x\n",
    "        while target:\n",
    "            target, cur = divmod(target, x)\n",
    "            if k:\n",
    "                pos, neg = min(cur * k + pos, (cur + 1) * k + neg), min((x - cur) * k + pos, (x - cur - 1) * k + neg)\n",
    "            else:\n",
    "                pos, neg = cur * 2, (x - cur) * 2\n",
    "            k += 1\n",
    "        return min(pos, k + neg) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, val):\n",
    "            if val == 0: return 0\n",
    "            base = 1 + abs(idx - 1)\n",
    "            if val == 1: return base\n",
    "            if idx > 30: return float('inf')\n",
    "            t, r = divmod(val, x)\n",
    "            return min(r * base + dfs(idx + 1, t), (x - r) * base + dfs(idx + 1, t + 1))\n",
    "        return dfs(0, target) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        \n",
    "        cost = list(range(40))\n",
    "        cost[0] = 2\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, ta: int) -> int:\n",
    "            if ta == 0: return 0\n",
    "            if ta == 1: return cost[i]\n",
    "            if i >= 39: return float('inf')\n",
    "\n",
    "            t, r = divmod(ta, x)\n",
    "            return min(r * cost[i] + dp(i+1, t),\n",
    "                       (x-r) * cost[i] + dp(i+1, t+1))\n",
    "\n",
    "        return dp(0, target) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        z = [1]\n",
    "        t = 1\n",
    "        while True:\n",
    "            t *= x\n",
    "            z.append(t)\n",
    "            if t > target:\n",
    "                break\n",
    "        \n",
    "        n = len(z)\n",
    "        @lru_cache(None)\n",
    "        def f(i: int, tgt: int) -> int:\n",
    "            if tgt == 0:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return abs(tgt * 2)\n",
    "            u = tgt // z[i]\n",
    "            return min([\n",
    "                abs(u + 1) * i + f(i - 1, tgt - (u + 1) * z[i]),\n",
    "                abs(u) * i + f(i - 1, tgt - u * z[i]),\n",
    "                abs(u - 1) * i + f(i - 1, tgt - (u - 1) * z[i])\n",
    "            ])\n",
    "        return f(n - 1, target) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur: int):\n",
    "            if cur < x:\n",
    "                return min(2*cur - 1, (x - cur)*2)\n",
    "            if cur == 0:\n",
    "                return 0\n",
    "            p = int(log(cur)/log(x))\n",
    "            s = x**p\n",
    "            ans = p + dfs(cur - s)\n",
    "            if s*x - cur < cur:\n",
    "                ans = min(ans, p + 1 + dfs(s*x - cur))\n",
    "            return ans\n",
    "        res = dfs(target)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\r\n",
    "        mx = int(math.log2(target)/math.log2(x))+1 #先确定x可能的最高幂次\r\n",
    "        def dfs(left):\r\n",
    "            if left<=x:\r\n",
    "                return min(2*left-1,2*(x-left))\r\n",
    "            pw = bisect_right(range(mx+1),left,key=lambda k: x**k) #找到最小的越过left的x的幂次\r\n",
    "            ans = 10**9\r\n",
    "            if x**pw-left<left:\r\n",
    "                ans = pw+dfs(x**pw-left) # 已经越过left，放上pw-1个乘号和一个减号，继续递归\r\n",
    "            ans = min(ans,pw-1+dfs(left-x**(pw-1))) # 还没到left，放上pw-2个乘号和一个加号，继续递归\r\n",
    "            return ans\r\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(v: int) -> int:\n",
    "            if x >= v:\n",
    "                return min(v * 2 - 1, 2 * (x - v))\n",
    "            k = 2\n",
    "            while x**k < v:\n",
    "                k += 1\n",
    "            if x**k - v < v:\n",
    "                return min(k + dfs(x**k - v), k - 1 + dfs(v - x ** (k - 1)))\n",
    "            return k - 1 + dfs(v - x ** (k - 1))\n",
    "\n",
    "        return dfs(target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur: int):\n",
    "            if cur < x:\n",
    "                return min(2*cur - 1, (x - cur)*2)\n",
    "            if cur == 0:\n",
    "                return 0\n",
    "            p = int(log(cur)/log(x))\n",
    "            s = x**p\n",
    "            ans = p + dfs(cur - s)\n",
    "            if s*x - cur < cur:\n",
    "                ans = min(ans, p + 1 + dfs(s*x - cur))\n",
    "            return ans\n",
    "        res = dfs(target)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dp(idx, t):\n",
    "            if t == 0:\n",
    "                return 0\n",
    "\n",
    "            cost = idx if idx > 0 else 2\n",
    "\n",
    "            if t == 1:\n",
    "                return cost\n",
    "\n",
    "            if idx > 40:\n",
    "                return inf\n",
    "\n",
    "            nt, r = divmod(t, x)\n",
    "\n",
    "            ret = inf\n",
    "            ret = min(ret, dp(idx + 1, nt) + r * cost)\n",
    "            ret = min(ret, dp(idx + 1, nt + 1) + (x - r) * cost)\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp(0, target) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "\n",
    "        max_target = 100*target\n",
    "\n",
    "        max_exp = int(math.log(max_target)/math.log(x))\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def DFS(i,target):\n",
    "            if target==0:\n",
    "                return 0  \n",
    "            if i>39:\n",
    "                return float(\"inf\")\n",
    "            y = x**i \n",
    "            z = x**(i+1)\n",
    "            add_op = i if i>0 else 2\n",
    "            rest = target%z\n",
    "            if rest==0:\n",
    "                return DFS(i+1, target)\n",
    "            else:\n",
    "                return min(add_op*(rest//y)+DFS(i+1,target-rest),\n",
    "                \n",
    "                 add_op*((z-rest)//y)+DFS(i+1,target+z-rest)   )\n",
    "        \n",
    "        return DFS(0,target)-1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\r\n",
    "\r\n",
    "        mx = int(math.log2(target)/math.log2(x))+1 #先确定x可能的最高幂次\r\n",
    "\r\n",
    "        @cache\r\n",
    "        def dfs(left):\r\n",
    "            if left<=x:\r\n",
    "                return min(2*left-1,2*(x-left))\r\n",
    "            pw = bisect_right(range(mx+1),left,key=lambda k: x**k) #找到最小的越过left的x的幂次\r\n",
    "            ans = 10**9\r\n",
    "            if x**pw-left<left:\r\n",
    "                ans = pw+dfs(x**pw-left) # 已经越过left，放上pw-1个乘号和一个减号，继续递归\r\n",
    "            ans = min(ans,pw-1+dfs(left-x**(pw-1))) # 还没到left，放上pw-2个乘号和一个加号，继续递归\r\n",
    "            return ans\r\n",
    "        \r\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur):\n",
    "            # 当cur < x, 比如 cur = 2, x = 3, 需要判断使用 3/3 + 3/3 和 3 - 3/3,哪个用运算符最少\n",
    "            if cur < x:\n",
    "                return min(2 * cur - 1, (x - cur) * 2)\n",
    "            if cur == 0:\n",
    "                return 0\n",
    "            # 到cur 需要几个x相乘,\n",
    "            p = int(math.log(cur, x))\n",
    "            sums = x ** p\n",
    "            # cur < sums 的情况,就是要加\n",
    "            ans = dfs(cur - sums) + p\n",
    "            # sums > cur, 就是要减去多少才能到底目标值, 这个判断条件是有严格的数学证明的\n",
    "            if sums * x - cur < cur:\n",
    "                ans = min(ans, p + 1 + dfs(sums * x - cur))\n",
    "            return ans\n",
    "\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "      @cache\n",
    "      def dfs(v: int) -> int:\n",
    "        # 用x凑成v的最少运算符\n",
    "        if x >= v:\n",
    "          return min(v * 2 - 1, 2 * (x - v))\n",
    "        k = 2\n",
    "        while x**k < v:\n",
    "          k += 1\n",
    "        if x**k - v < v:\n",
    "          return min(k + dfs(x**k - v), k - 1 + dfs(v - x**(k - 1)))\n",
    "        return k - 1 + dfs(v - x**(k - 1))\n",
    "      \n",
    "      return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(x,target):\n",
    "            if target == x:\n",
    "                return 0\n",
    "            #                 x > target ， 以下两种情况去最小\n",
    "            # (1) x/x + x/x + ... x/x (运算符数量是 2*target-1)\n",
    "            # (2) x - x/x - x/x ... -x/x (运算符数量是 2*（x-target))\n",
    "            #  x - target + 1项 2*(x - target + 1) - 2\n",
    "            if x > target:\n",
    "                return min(2*target - 1,2*(x - target))\n",
    "            else:\n",
    "                cnt = 0\n",
    "                xp = x\n",
    "                while xp < target:\n",
    "                    xp *= x\n",
    "                    cnt += 1\n",
    "                if xp - target >= target:\n",
    "                    return cnt - 1 + dfs(x,target - xp // x) + 1 \n",
    "                else:\n",
    "                    return min(cnt - 1 + dfs(x,target - xp // x),cnt + dfs(x,xp - target)) + 1\n",
    "            \n",
    "        return dfs(x,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(target):\n",
    "            if target == x:\n",
    "                return 0\n",
    "            #                 x > target ， 以下两种情况去最小\n",
    "            # (1) x/x + x/x + ... x/x (运算符数量是 2*target-1)\n",
    "            # (2) x - x/x - x/x ... -x/x (运算符数量是 2*（x-target))\n",
    "            #  x - target + 1项 2*(x - target)\n",
    "            if x > target:\n",
    "                return min(2*target - 1,2*(x - target))\n",
    "            else:\n",
    "                cnt = 0\n",
    "                xp = x\n",
    "                while xp < target:\n",
    "                    xp *= x\n",
    "                    cnt += 1\n",
    "                if xp - target >= target:\n",
    "                    return cnt - 1 + dfs(target - xp // x) + 1 \n",
    "                else:\n",
    "                    return min(cnt - 1 + dfs(target - xp // x) + 1,cnt + dfs(xp - target) + 1)\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def leastOpsExpressTarget(self, x: int, target: int) -> int:\r\n",
    "\r\n",
    "        mx = int(math.log2(target)/math.log2(x))+1 #先确定x可能的最高幂次\r\n",
    "\r\n",
    "        @cache\r\n",
    "        def dfs(left):\r\n",
    "            if left<=x:\r\n",
    "                return min(2*left-1,2*(x-left))\r\n",
    "            pw = bisect_right(range(mx+1),left,key=lambda k: x**k) #找到最小的越过left的x的幂次\r\n",
    "            ans = 10**9\r\n",
    "            if x**pw-left<left:\r\n",
    "                ans = pw+dfs(x**pw-left) # 已经越过left，放上pw-1个乘号和一个减号，继续递归\r\n",
    "            ans = min(ans,pw-1+dfs(left-x**(pw-1))) # 还没到left，放上pw-2个乘号和一个加号，继续递归\r\n",
    "            return ans\r\n",
    "        \r\n",
    "        return dfs(target)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
